#pragma once
//#include "stdlib.h"
#define NULL 0
#pragma region Node
template< class T >
struct Node
{
public:
	T* m_Data;
	Node* m_NextNode;
	Node* m_PreviousNode;
	int m_ID;
};
#pragma endregion

#pragma region LinkedList
template< class T >
class LinkedList
{
public:
	//csruct dstruct
	LinkedList();
	~LinkedList();
	//Functions
	void AddFront( T* a_Data );
	void AddEnd( T* a_Data );
	void AddAt( T* a_Data, int a_Index );
	void DeleteFront();
	void DeleteEnd();
	void DeleteAt( int a_Index );
	void Refresh();
	void Merge( LinkedList<T>* a_List, bool a_Duplicate  );
	void DeleteObject( T* a_Data );
	Node<T>* FirstNode() { return m_FirstNode; }
	Node<T>* LastNode() { return m_LastNode; }
	Node<T>* IndexNode( int a_Index );
	void Clear();
	int Length() { return m_NodeCount; } 

private:
	//Variables
	Node<T>* m_FirstNode;
	Node<T>* m_LastNode;
	int m_NodeCount;
};

template< class T >
LinkedList<T>::LinkedList()
{
	m_FirstNode = NULL;
	m_LastNode = NULL;
	m_NodeCount = 0;
}

template< class T >
LinkedList<T>::~LinkedList()
{
	Clear();
	delete m_FirstNode;
	delete m_LastNode;
}

template< class T >
void LinkedList<T>::AddFront( T* a_Data )
{
	//Check if the list is empty
	if ( m_FirstNode == NULL ) 
	{
		//Create a fresh node
		Node<T>* NewNode = new Node<T>();
		NewNode->m_Data = a_Data;
		NewNode->m_NextNode = NULL;
		NewNode->m_PreviousNode = NULL;
		NewNode->m_ID = Length();
		m_FirstNode = NewNode;	
		m_LastNode = NewNode;
	}
	else
	{
		//Create a fresh node
		Node<T>* NewNode = new Node<T>();
		NewNode->m_Data = a_Data;
		NewNode->m_NextNode = m_FirstNode;
		NewNode->m_PreviousNode = NULL;
		NewNode->m_ID = Length();
		m_FirstNode->m_PreviousNode = NewNode;		
		m_FirstNode = NewNode;		
	}

	//Increase the node count ( list length )
	m_NodeCount++; 
	Refresh();
}

template< class T >
void LinkedList<T>::AddEnd( T* a_Data )
{
	//The list won't be empty but do check it
	if ( m_FirstNode == NULL )
	{
		//Create a fresh node
		Node<T>* NewNode = new Node<T>();
		NewNode->m_Data = a_Data;
		NewNode->m_NextNode = NULL;
		NewNode->m_PreviousNode = NULL;
		NewNode->m_ID = Length();
		m_FirstNode = NewNode;	
		m_LastNode = NewNode;
	}
	else
	{
		//Create a fresh node
		Node<T>* NewNode = new Node<T>();
		NewNode->m_Data = a_Data;
		NewNode->m_PreviousNode = m_LastNode;
		NewNode->m_NextNode = NULL;
		NewNode->m_ID = Length();
		m_LastNode->m_NextNode = NewNode;
		m_LastNode = NewNode;		
	}

	//Increase the node count ( list length )
	m_NodeCount++; 
	//Refresh();
}

//Change this or remove it
template< class T >
void LinkedList<T>::AddAt( T* a_Data, int a_Index )
{
	//See if the index isn't out of range
	if ( a_Index < Length() )
	{
		Node<T>* PreviousNode;
		PreviousNode = (Node<T>*) m_FirstNode;
		while ( a_Index != PreviousNode->m_ID )
		{
			PreviousNode = PreviousNode->m_NextNode;
		}

		//Set the previous and next pointers
		Node<T>* NewNode = new Node<T>();
		NewNode->m_Data = a_Data;
		NewNode->m_ID = a_Index;
		NewNode->m_PreviousNode = PreviousNode;
		NewNode->m_NextNode = PreviousNode->m_NextNode;

		//Now change the old node's pointers
		if ( PreviousNode->m_NextNode != NULL )
		{
			PreviousNode->m_NextNode->m_PreviousNode = NewNode;
		}
		PreviousNode->m_NextNode = NewNode;

		//Increase the node count ( list length )
		m_NodeCount++; 
		Refresh();
	}
}

template< class T >
void LinkedList<T>::DeleteFront()
{
	//Remove the item
	//Placeholder for the 2nd node
	Node<T>* DeleteNode;
	if ( m_FirstNode->m_NextNode != NULL ) 
	{
		DeleteNode = m_FirstNode->m_NextNode;
		DeleteNode->m_PreviousNode = NULL;
		//Delete the first node
		//delete m_FirstNode->m_Data;
		delete m_FirstNode;
		//Now replace it with the placeholder we created
		m_FirstNode = DeleteNode;
	}
	else
	{
//		delete m_FirstNode->m_ID;
		//delete m_FirstNode;
	}

	m_NodeCount--;
}

template< class T >
void LinkedList<T>::DeleteEnd()
{
	//Remove the item
	//Placeholder for the second last node
	Node<T>* DeleteNode;
	if ( m_LastNode->m_PreviousNode != NULL ) //Only one left in the list
	{
		DeleteNode = m_LastNode->m_PreviousNode;
		DeleteNode->m_NextNode = NULL;		
	}
	else
	{
		DeleteNode = NULL;
	}
	//Delete the current last node
	//delete m_LastNode->m_Data;
	delete m_LastNode->m_Data;
	delete m_LastNode;
	
	//Replace the deleted note with the placeholder
	m_LastNode = DeleteNode;	
	m_NodeCount--;
}

template< class T >
void LinkedList<T>::DeleteAt( int a_Index )
{
	//Check if the index isn't out of range
	if ( a_Index < Length() ) 
	{
		Node<T>* DeleteNode;
		DeleteNode = m_FirstNode;
		//Loop through the list till we find the given index ( ID )
		while ( a_Index != DeleteNode->m_ID )
		{
			DeleteNode = DeleteNode->m_NextNode;
		}
		//Now delete it
		//Make the pointers on both left and right of the current item point to eachother
		if ( DeleteNode->m_PreviousNode != NULL )
		{
			DeleteNode->m_PreviousNode->m_NextNode = DeleteNode->m_NextNode;
		}
		if ( DeleteNode->m_NextNode != NULL )
		{
			DeleteNode->m_NextNode->m_PreviousNode = DeleteNode->m_PreviousNode;
		}
		//And delete the data / used memory
		//delete DeleteNode->m_Data;
		//delete DeleteNode;

		Refresh();
	}	
}

template< class T >
void LinkedList<T>::Clear()
{
	while ( Length() != 0 )
	{
		DeleteFront();
	}
}

template< class T >
Node<T>* LinkedList<T>::IndexNode( int a_Index )
{
	//Check if the list is empty checking the first node and the count
	if ( m_FirstNode == NULL || m_NodeCount == 0 )
	{
		return NULL;
	}
	else
	{
		Node<T>* IndexNode = new Node<T>();
		IndexNode = m_FirstNode;
		//Run till the given index
		while ( IndexNode->m_ID != a_Index )
		{
			IndexNode = IndexNode->m_NextNode;			
		}
		return IndexNode;
	}	
}

template< class T >
void LinkedList<T>::Refresh()
{
	//Run through the list and reset the id's 
	Node<T>* RefreshNode;
	RefreshNode = m_FirstNode;
	for ( int i = 0; i < Length(); i++ )
	{
	/*	if ( RefreshNode->m_Data == NULL )
		{

		}
*/
		RefreshNode->m_ID = i;
		RefreshNode = RefreshNode->m_NextNode;
		
	}
}
template< class T>
void LinkedList<T>::Merge( LinkedList<T>* a_List, bool a_Duplicate )
{
	if ( a_List->Length() != 0)
	{
		if ( a_Duplicate == false ) //We don't want duplicates while mergin
		{
			Iterator< T >* NewIt = new Iterator< T >( a_List, 0 );
			Iterator< T >* It = new Iterator< T >( this, 0 );
			do 
			{
				bool Duplicate = false;
				if ( this->Length() != 0 )
				{			
					do 
					{
						if ( It->CurrentNode()->m_Data == NewIt->CurrentNode()->m_Data )
						{
							Duplicate = true;
							break;
						}
					} 
					while ( It->Loop() );
				}

				if ( Duplicate == false )
				{
					this->AddFront( NewIt->CurrentNode()->m_Data );
					this->Refresh();
					It->First();
				}
			}			
			while ( NewIt->Loop() );
		}
		else //Just link the head and tail
		{
			if ( m_FirstNode == NULL ) //Merging an empty list with another one
			{
				m_FirstNode = a_List->FirstNode();
				m_LastNode = a_List->LastNode();
			}
			else
			{
				this->m_LastNode->m_NextNode = a_List->m_FirstNode;
				a_List->m_FirstNode->m_PreviousNode = m_LastNode;
				this->m_LastNode = a_List->LastNode();	
			}
					
		}	
	}
	
	
}

template< class T >
void LinkedList<T>::DeleteObject( T* a_Data )
{
	if ( m_NodeCount == 1 )
	{
		m_FirstNode = NULL;
		m_LastNode = NULL;
		m_NodeCount = 0;
		return;
	}

	Iterator< T >* It = new Iterator< T >( this, 0 );
	do 
	{
		if ( It->CurrentNode()->m_Data == a_Data )
		{
		
			if ( It->CurrentNode()->m_PreviousNode != NULL ) //Isn't the first one in the list
			{
				It->CurrentNode()->m_NextNode->m_PreviousNode = It->CurrentNode()->m_PreviousNode;
			}
			else
			{
				It->CurrentNode()->m_NextNode->m_PreviousNode = NULL;
				m_FirstNode = It->CurrentNode()->m_NextNode;
			}

			if ( It->CurrentNode()->m_NextNode != NULL ) //Isn't the last one in list
			{
				It->CurrentNode()->m_PreviousNode->m_NextNode = It->CurrentNode()->m_NextNode;
			}
			else
			{
				It->CurrentNode()->m_PreviousNode->m_NextNode = NULL;
				m_LastNode = It->CurrentNode()->m_PreviousNode;
			}

			//Refresh();
			m_NodeCount--;
			return;
		}
	} while ( It->Loop() );
}
#pragma endregion

#pragma region Iterator
template< class T >
class Iterator
{
public:
	Iterator( LinkedList<T>* a_List, int a_Index );
	~Iterator();
	Node<T>* CurrentNode() { return m_CurrentNode; }
	int GetIndex() { return m_Index; }
	bool Loop();
	bool LoopBackFront();
	void First();
	void NextNode();
private:
	LinkedList<T>* m_List;
	int m_Index;
	Node<T>* m_CurrentNode;
};

template< class T >
inline void Iterator<T>::NextNode()
{
	m_CurrentNode = m_CurrentNode->m_NextNode;
}

template< class T >
Iterator<T>::Iterator( LinkedList<T>* a_List, int a_Index )
{
	m_List = a_List;
	m_Index = a_Index;
	m_CurrentNode = m_List->IndexNode( a_Index );

}

template< class T >
Iterator<T>::~Iterator()
{
	delete m_List;
	delete m_CurrentNode;
}

template< class T >
bool Iterator<T>::Loop()
{
	//Check if this is the last item in the list
	if( m_CurrentNode != NULL && m_CurrentNode->m_NextNode != NULL )
	{
		m_CurrentNode = m_CurrentNode->m_NextNode;		
		return true;
	}
	//And then return false and reset the iterator to the first item in the list
	else
	{
		m_CurrentNode = m_List->FirstNode();
		return false;
	}
}

template< class T >
bool Iterator<T>::LoopBackFront()
{
	//Check if this is the first item in the list
	if( m_CurrentNode != NULL && m_CurrentNode->m_PreviousNode != NULL )
	{
		m_CurrentNode = m_CurrentNode->m_PreviousNode;
		return true;
	}
	//And return false if it is the first item ( last to loop through )
	else
	{
		m_CurrentNode = m_List->LastNode();
		return false;
	}
}

template< class T>
void Iterator<T>::First()
{
	m_CurrentNode = m_List->FirstNode();
}
#pragma endregion